package graph.impl;

import graph.core.IEdge;
import graph.core.IGraph;
import graph.core.IIterator;
import graph.core.IList;
import graph.core.IPosition;
import graph.core.IVertex;
import graph.util.DLinkedList;

/**
 * Adjacency Matrix implementation of the Graph data structure.
 * 
 * Uses a two-dimensional array to store edge relationships between vertices.
 * This implementation is suitable for dense graphs (number of edges close to
 * |V|²).
 * 
 * Time complexity:
 * - areAdjacent: O(1) - Direct matrix lookup provides constant time
 * - incidentEdges: O(|V|) - Must scan a row/column of the matrix
 * - insertEdge/removeEdge: O(1) - Direct matrix access
 * - insertVertex: O(1) typically, but O(|V|²) when expansion occurs
 * - removeVertex: O(|V|²) - Need to restructure the matrix
 * 
 * Feature: When the number of vertices exceeds the matrix capacity,
 * the matrix size will automatically expand by doubling its dimensions.
 */
public class AdjacencyMatrixGraph<V, E> implements IGraph<V, E> {
    /**
     * Inner class to represent a vertex in an adjacency matrix graph
     * implementation.
     * Each vertex stores its element and maintains its position in the matrix.
     */
    private class AMVertex implements IVertex<V> {
        // reference to a node in the vertex list
        IPosition<IVertex<V>> node;

        // element stored in this vertex
        V element;

        // index of the vertex in the matrix - critical for O(1) access
        int index;

        /**
         * Creates a new vertex with the given element and index in the matrix
         * 
         * @param element The data element to store in this vertex
         * @param index   The position index in the adjacency matrix
         */
        public AMVertex(V element, int index) {
            this.element = element;
            this.index = index;
        }

        @Override
        public V element() {
            return element;
        }

        public String toString() {
            return element.toString();
        }
    }

    /**
     * Inner class to represent an edge in an adjacency matrix graph implementation.
     * Each edge stores its element and the vertices it connects.
     */
    private class AMEdge implements IEdge<E> {
        // reference to a node in the edge list
        IPosition<IEdge<E>> node;

        // element stored in this edge
        E element;

        // the start and end vertices that this edge connects
        AMVertex start, end;

        /**
         * Creates a new edge connecting the specified vertices with the given element
         * 
         * @param start   The first vertex this edge connects
         * @param end     The second vertex this edge connects
         * @param element The data element to store in this edge
         */
        public AMEdge(AMVertex start, AMVertex end, E element) {
            this.start = start;
            this.end = end;
            this.element = element;
        }

        @Override
        public E element() {
            return element;
        }

        public String toString() {
            return element.toString();
        }
    }

    // vertex list - maintains the collection of all vertices
    private IList<IVertex<V>> vertices;

    // edge list - maintains the collection of all edges
    private IList<IEdge<E>> edges;

    // adjacency matrix - stores references to edges between vertices
    private Object[][] matrix;

    // current capacity of the matrix
    private int capacity;

    // default initial capacity
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Constructor - initializes the graph with default capacity
     */
    public AdjacencyMatrixGraph() {
        vertices = new DLinkedList<IVertex<V>>();
        edges = new DLinkedList<IEdge<E>>();
        capacity = DEFAULT_CAPACITY;
        matrix = new Object[capacity][capacity];
    }

    /**
     * Expands the matrix size by doubling its dimensions when needed.
     * This is called when the current vertex count approaches the matrix capacity.
     * Time complexity: O(n²) where n is the current capacity.
     */
    private void expandMatrix() {
        int newCapacity = capacity * 2;
        Object[][] newMatrix = new Object[newCapacity][newCapacity];

        // copy the contents of the old matrix to the new matrix
        for (int i = 0; i < capacity; i++) {
            for (int j = 0; j < capacity; j++) {
                newMatrix[i][j] = matrix[i][j];
            }
        }

        matrix = newMatrix;
        capacity = newCapacity;
    }

    /**
     * Returns the end vertices of the specified edge.
     * 
     * @param e The edge whose endpoints we want to find
     * @return An array containing the two endpoint vertices
     */
    @Override
    public IVertex<V>[] endVertices(IEdge<E> e) {
        AMEdge edge = (AMEdge) e;

        @SuppressWarnings("unchecked")
        IVertex<V>[] endpoints = new IVertex[2];

        endpoints[0] = edge.start;
        endpoints[1] = edge.end;

        return endpoints;
    }

    /**
     * Returns the vertex opposite to the specified vertex along the given edge.
     * 
     * @param v The known vertex
     * @param e The edge connecting the known vertex to its opposite
     * @return The opposite vertex
     * @throws RuntimeException if the vertex is not incident to the edge
     */
    @Override
    public IVertex<V> opposite(IVertex<V> v, IEdge<E> e) {
        AMEdge edge = (AMEdge) e;

        if (edge.start.equals(v)) {
            return edge.end;
        } else if (edge.end.equals(v)) {
            return edge.start;
        }

        throw new RuntimeException("Error: cannot find opposite vertex.");
    }

    /**
     * Checks if two vertices are adjacent (connected by an edge).
     * Takes advantage of the O(1) lookup in the adjacency matrix.
     * 
     * @param v First vertex
     * @param w Second vertex
     * @return true if the vertices are adjacent, false otherwise
     */
    @Override
    public boolean areAdjacent(IVertex<V> v, IVertex<V> w) {
        AMVertex v1 = (AMVertex) v;
        AMVertex v2 = (AMVertex) w;

        return matrix[v1.index][v2.index] != null || matrix[v2.index][v1.index] != null;
    }

    /**
     * Replaces the element in a vertex with a new element.
     * 
     * @param v The vertex whose element is to be replaced
     * @param x The new element
     * @return The old element
     */
    @Override
    public V replace(IVertex<V> v, V x) {
        AMVertex vertex = (AMVertex) v;
        V temp = vertex.element;
        vertex.element = x;
        return temp;
    }

    /**
     * Replaces the element in an edge with a new element.
     * 
     * @param e The edge whose element is to be replaced
     * @param x The new element
     * @return The old element
     */
    @Override
    public E replace(IEdge<E> e, E x) {
        AMEdge edge = (AMEdge) e;
        E temp = edge.element;
        edge.element = x;
        return temp;
    }

    /**
     * Inserts a new vertex with the given element into the graph.
     * Expands the matrix if necessary.
     * 
     * @param v The element to be stored in the new vertex
     * @return The newly created vertex
     * @throws IllegalArgumentException if the element is null
     */
    @Override
    public IVertex<V> insertVertex(V v) {
        if (v == null) {
            throw new IllegalArgumentException("Vertex element cannot be null");
        }

        // Check if matrix expansion is needed
        if (vertices.size() >= capacity) {
            expandMatrix();
        }

        // Create new vertex
        AMVertex vertex = new AMVertex(v, vertices.size());
        IPosition<IVertex<V>> node = vertices.insertLast(vertex);
        vertex.node = node;

        return vertex;
    }

    /**
     * Inserts a new edge connecting the specified vertices with the given element.
     * 
     * @param v The first vertex
     * @param w The second vertex
     * @param o The element to be stored in the new edge
     * @return The newly created edge
     * @throws IllegalArgumentException if vertices are null, already adjacent, or
     *                                  same vertex (self-loop)
     */
    @Override
    public IEdge<E> insertEdge(IVertex<V> v, IVertex<V> w, E o) {
        if (v == null || w == null) {
            throw new IllegalArgumentException("Vertices cannot be null");
        }

        // Attempt type conversion
        AMVertex start, end;
        try {
            start = (AMVertex) v;
            end = (AMVertex) w;
        } catch (ClassCastException e) {
            throw new IllegalArgumentException("Vertex type mismatch");
        }

        // Check if edge already exists or is a self-loop
        if (matrix[start.index][end.index] != null || start == end) {
            throw new IllegalArgumentException("Vertices already adjacent or attempting to create a self-loop");
        }

        // Create new edge
        AMEdge edge = new AMEdge(start, end, o);

        // Add edge to edge list
        IPosition<IEdge<E>> node = edges.insertLast(edge);
        edge.node = node;

        // Store edge reference in adjacency matrix
        matrix[start.index][end.index] = edge;
        matrix[end.index][start.index] = edge; // Undirected graph

        return edge;
    }

    /**
     * Removes a vertex and all its incident edges from the graph.
     * This is a complex operation as it requires restructuring the adjacency
     * matrix.
     * 
     * @param v The vertex to be removed
     * @return The element of the removed vertex
     */
    @Override
    public V removeVertex(IVertex<V> v) {
        AMVertex vertex = (AMVertex) v;
        int index = vertex.index;

        // Remove all edges incident to this vertex
        for (int i = 0; i < vertices.size(); i++) {
            if (matrix[index][i] != null) {
                removeEdge((AMEdge) matrix[index][i]);
            }
            if (matrix[i][index] != null && i != index) {
                removeEdge((AMEdge) matrix[i][index]);
            }
        }

        // Remove vertex from vertex list
        vertices.remove(vertex.node);

        // Update indices of remaining vertices and restructure the matrix
        IIterator<IVertex<V>> it = vertices.iterator();
        int newIndex = 0;
        while (it.hasNext()) {
            AMVertex v1 = (AMVertex) it.next();
            if (v1.index > index) {
                v1.index--;
            }

            // Restructure matrix by shifting rows and columns
            for (int j = 0; j < vertices.size() + 1; j++) {
                if (v1.index >= index && j < vertices.size() + 1) {
                    if (j >= index && j < vertices.size()) {
                        matrix[v1.index][j] = matrix[v1.index + 1][j + 1];
                    } else if (j < index) {
                        matrix[v1.index][j] = matrix[v1.index + 1][j];
                    }
                } else if (v1.index < index && j >= index && j < vertices.size()) {
                    matrix[v1.index][j] = matrix[v1.index][j + 1];
                }
            }
        }

        return vertex.element;
    }

    /**
     * Removes an edge from the graph.
     * 
     * @param e The edge to be removed
     * @return The element of the removed edge
     */
    @Override
    public E removeEdge(IEdge<E> e) {
        AMEdge edge = (AMEdge) e;

        // Remove edge reference from adjacency matrix
        matrix[edge.start.index][edge.end.index] = null;
        matrix[edge.end.index][edge.start.index] = null;

        // Remove edge from edge list
        edges.remove(edge.node);

        return edge.element;
    }

    /**
     * Returns an iterator over all edges incident to the specified vertex.
     * Time complexity: O(|V|) as we need to scan a row of the matrix.
     * 
     * @param v The vertex whose incident edges we want to find
     * @return An iterator over the incident edges
     */
    @Override
    public IIterator<IEdge<E>> incidentEdges(IVertex<V> v) {
        AMVertex vertex = (AMVertex) v;
        IList<IEdge<E>> incidentList = new DLinkedList<IEdge<E>>();

        // Scan the corresponding row of the matrix to find all connected edges
        for (int i = 0; i < vertices.size(); i++) {
            if (matrix[vertex.index][i] != null) {
                incidentList.insertLast((AMEdge) matrix[vertex.index][i]);
            }
        }

        return incidentList.iterator();
    }

    /**
     * Returns an iterator over all vertices in the graph.
     * 
     * @return An iterator over all vertices
     */
    @Override
    public IIterator<IVertex<V>> vertices() {
        return vertices.iterator();
    }

    /**
     * Returns an iterator over all edges in the graph.
     * 
     * @return An iterator over all edges
     */
    @Override
    public IIterator<IEdge<E>> edges() {
        return edges.iterator();
    }
}